//重建二叉树: https://www.nowcoder.com/practice/8a19cbe657394eeaac2f6ea9b0f6fcf6?
/**
 * struct TreeNode {
 *  int val;
 *  struct TreeNode *left;
 *  struct TreeNode *right;
 *  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
  public:
    TreeNode* reConstructBinaryTreeCore(vector<int> pre, int preStart, int preEnd, vector<int> vin, int vinStart, int vinEnd) {
        if (preStart > preEnd || vinStart > vinEnd) 
        {
            return nullptr;
        }

        TreeNode* root = new TreeNode(pre[preStart]);
        for (auto i = vinStart; i <= vinEnd; i++) 
        {
            //在中序序列中，找根节点，可以将数组划分为两部分
            if (pre[preStart] == vin[i]) 
            {
                // 前序的第一个节点，是root，能将中序划分为两部分
                // 一棵树，无论前，中，后怎么遍历，元素的个数是不变的
                // 在实际遍历的时候，前，中，后序遍历，各种遍历方式左右子树的节点都是在一起的
                // 所以这里重点是要想清楚下标问题
                // 根据中序，我们能确认左子树的节点个数是：i - vinStart (没有从0开始哦)
                // 所以，需要从preStart+1，连续i - vinStart个元素，就是左子树的前序序列
                root->left = reConstructBinaryTreeCore(pre, preStart + 1, i - vinStart + preStart, vin, vinStart, i - 1);
                root->right = reConstructBinaryTreeCore(pre, i - vinStart + preStart + 1, preEnd, vin, i + 1, vinEnd);
                break;
            }
        }
        return root;
    }

    TreeNode* reConstructBinaryTree(vector<int> pre, vector<int> vin) 
    {
        if (pre.empty() || vin.empty()) 
        {
            return nullptr;
        }
        return reConstructBinaryTreeCore(pre, 0, pre.size() - 1, vin, 0, vin.size() - 1);
    }

};